Batch 3 - Class 108 - Dropping Eggs, Jelly Beans - Solving large problems by solving small ones
Pre-Class Problem:
In a far away land, it was known that if you drank poison, the only way to save yourself is to drink a stronger poison, which neutralizes the weaker poison. The king that ruled the land wanted to make sure that he possessed the strongest poison in the kingdom, in order to ensure his survival, in any situation. So the king called the kingdom's pharmacist and the kingdom's sage, he gave each a week to make the strongest poison. Then, each would drink the other one's poison, then his own, and the one that will survive, will be the one that had the stronger poison. The pharmacist went straight to work, but the sage knew he had no chance, for the pharmacist was much more experienced in this field, so instead, he made up a plan to survive and make sure the pharmacist dies. On the last day the pharmacist suddenly realized that the sage would know he had no chance, so he must have a plan. After a little thought, the pharmacist realized what the sage's plan must be, and he concocted a counter plan, to make sure he survives and the sage dies. When the time came, the king summoned both of them. They drank the poisons as planned, and the sage died, the pharmacist survived, and the king didn't get what he wanted.
What exactly happened there?
Answer: The sage's plan: He made a weak poison and drank it just before the test. During the test time, he would drink the stronger poison which he thinks the pharmacist would have made. Meanwhile, he takes a non-poisonous drink to the test and presents it as his poison. In this case the pharmacist would drink it and then drink his own poison and die.
The pharmacist's plan: He knows that the sage is going to drink a weak poison before the test and that he is going to present a non-poisonous drink. So the pharmacist counters this by presenting a non-poisonous drink too effectively disabling the sage from countering the poison he consumed earlier.
Imagine you're a farmer and you've produced a breed of hen that lays particularly strong eggs. You want to test just how strong those eggs are by throwing them off the various floors of a 100-story building. Your task is to find the highest floor you can drop an egg from without breaking it. If you had just one egg, you'd know how you would do this: first throw the egg off the 1st floor, if it doesn't break move up to the second, then the third, and so on. You'd need at most 100 throws to find the answer.
But now suppose you had two eggs. What strategy would you use to find the highest drop an egg can survive? What's the smallest number of egg throws you can get away with?
Instructor Notes: Let kids try a smaller problem first. Perhaps 3 floors (doable with two drops), and then 10 floors (doable with 4 eggs). That should allow them to start putting a pattern
Kids should also be able to realize that if they throw too high and it breaks, then they have a lot of floors to cover with the second egg. Conversely, if they throw too low and it does not break, then they have used up a throw for cheap. So some kind of a balance needs to be struck
Answer: Lets say you make the first drop from nth floor. If it breaks then you have to test using the second egg from floor 1 onwards, upto (n-1) in worst case. This means total of n drops. If it doesn't break, then we must make the second drop by going up another (n-1) floors, so that if it breaks, we can use the second egg (n-2) times [from (n+1)th to (n+n-1-1) floors] to again preserve total n drops. And so on. So total number of throws would be n+(n-1)+(n-2)...+1 which should get us to top of the building, i.e. 100. This solves for n=13.something - hence n=14 is a good answer. This requires maximum 14 drops to figure out what height will the egg break at.
The Jelly Bean Jar
There is a retired mathematician who owns a candy store in your town. Not only does she sell amazing sweets, but she is also known to give challenging puzzles to all her customers. One day, in the display window is a large jar of jelly beans — a very large jar of jelly beans. And, as one might guess, there is a contest to see who can figure out how many jelly beans there are in this oversize jar. It’s not a contest to see who can come closest, it’s a contest to see who can actually figure out the exact amount.
There is a clue that is written on the jar.
“Starting tomorrow I will remove some jelly beans from the jar. The next day a random customer will remove some. Then the day after, I will remove some more. Every other day I will alternate removing jelly beans with my customers. The only rule is that nobody, including myself, can remove more than half of the remaining jelly beans. The only other thing that I can tell you is that when there is one jelly bean left, I can guarantee 100 percent that it will not be my turn to remove jelly beans! The jar is big. It contains between five and eight thousand jelly beans. Tomorrow I will remove 1,111 jelly beans.”
How many jelly beans are in the jar?
Answer: Note that if the store owner leaves 2^n-1 beans in the jar, then regardless of what the customer does, she can leave 2^(n-1)-1 the next day, and so on. This will finally result in leaving 1 for the customer to pick. The power of two between 5000 and 8000 is 4096, and hence initial number of candies must be 4096-1+1111=5206
Kids can also arrive at this solution by working backwards. To leave 1 candy, she must get back 2 candies from the customer. Which means the the customer must get back 3. To ensure that the storeowner can return 3, she must get back 4,5 or 6. This can be achieved if she has given 7 to the customer the prior day. This series 1, 3, 7 and so on is of the form 2^n-1
Homework
(Contributed by Ishaan) In a two player game, each player picks a prime number of pebbles from a given pile. Assuming both players are super smart, who will win the game starting with 105 pebbles in the pile?